package MyGraph;

import java.util.Scanner;

public class ALGraph implements IGraph{
    // 图的四种基本类型
    public enum graphKind{
        UDG, // 无向图
        DG, // 有向图
        UDN, // 无向网
        DN  // 有向网
    }

    // 图的类型
    private graphKind kind;

    // 顶点数
    private int vNum;
    // 边数
    private int eNum;

    // 顶点集合
    private VNode[] v;

    public ALGraph() {
        this(null, 0, 0, null);
    }

    public ALGraph(graphKind kind, int vNum, int eNum, VNode[] v) {
        this.kind = kind;
        this.vNum = vNum;
        this.eNum = eNum;
        this.v = v;
    }


    // 创建图
    public void createGraph() {
        switch (kind){
            case DG:
                createDG();
                break;
            case DN:
                createDN();
                break;
            case UDG:
                createUDG();
                break;
            case UDN:
                createUDN();
                break;
        }

    }


    // 创建有向网
    private void createDN(){
        Scanner sc = new Scanner(System.in);
        // 顶点数量
        vNum = sc.nextInt();
        // 边的数量
        eNum = sc.nextInt();
        // 构造顶点集
        v = new VNode[vNum];
        for(int i=0; i<vNum; i++){
            v[i] = new VNode(sc.next());
        }

        // 构造边链表
        for(int i=0; i<eNum; i++){
            int u = locateVex(sc.nextInt());
            int v = locateVex(sc.nextInt());
            int k = sc.nextInt();
            addArc(u, v, k);
        }
    }

    // 创建无向网
    private void createUDN(){
        Scanner sc = new Scanner(System.in);
        // 顶点数量
        vNum = sc.nextInt();
        // 边的数量
        eNum = sc.nextInt();
        // 构造顶点集
        v = new VNode[vNum];
        for(int i=0; i<vNum; i++){
            v[i] = new VNode(sc.next());
        }

        // 构造边链表
        for(int i=0; i<eNum; i++){
            int u = locateVex(sc.nextInt());
            int v = locateVex(sc.nextInt());
            int k = sc.nextInt();
            addArc(u, v, k);
            addArc(v, u, k);
        }
    }

    // 创建无向图
    private void createUDG(){
        Scanner sc = new Scanner(System.in);
        // 输入顶点个数
        vNum = sc.nextInt();
        // 输入的边数
        eNum = sc.nextInt();
        // 构造顶点集
        v = new VNode[vNum];

        for(int i=0; i<vNum; i++){
            v[i] = new VNode(sc.next());
        }

        for(int i=0; i<eNum; i++){
            int u = locateVex(sc.nextInt());
            int v = locateVex(sc.nextInt());

            addArc(u, v, 1);
            addArc(v, u, 1);
        }

    }

    // 创建有向图
    private void createDG(){
        Scanner sc = new Scanner(System.in);
        // 输入顶点的数
        vNum = sc.nextInt();
        // 输入边的数
        eNum = sc.nextInt();
        // 构造顶点集
        v = new VNode[vNum];

        // 构造边链表
        for(int i=0; i<vNum; i++){
            int u = locateVex(sc.nextInt());
            int v = locateVex(sc.nextInt());
            addArc(u, v, 1);

        }

    }


    // 返回顶点数
    public int getVNum() {
        return vNum;
    }

    // 返回边数
    public int getENum() {
        return eNum;
    }

    // 返回第i个订点的值
    public Object getVex(int i) throws Exception {
        if(i<0 || i>=vNum){
            throw new Exception("第"+ i +"个顶点不存在");
        }
        return v[i].data;
    }

    // 返回值为x的订点的位置
    public int locateVex(Object x) {
        for(int i=0; i<vNum; i++){
            if (v[i].data.equals(x)) {
                return i;
            }
        }
        return -1;
    }

    // 返回第i个顶点的第一个邻接点
    public int firstAdj(int i) throws Exception {
        if(i<0 || i>=vNum){
            throw new Exception("第"+ i +"个结点不存在");
        }
        ArcNode p = v[i].firstArc;
        if(p != null){
            return p.adjVex;
        }
        return -1;
    }

    // 返回i相对于j的下一个邻接点
    public int nextAdj(int i, int j) {
        ArcNode p = v[i].firstArc;
        for(; p!=null; p=p.nextArc){
            if(p.adjVex == j){
                break;
            }
        }
        if(p!=null){
            return p.nextArc.adjVex;
        }
        return -1;
    }


    // 插入边结点
    public void addArc(int i, int j, int value){
        // 建立边结点
        ArcNode arc = new ArcNode(j, value);
        // 把arc的 下一条边指向 v[i]
        arc.nextArc = v[i].firstArc;;
        v[i].firstArc = arc;
    }




}
